 package leetcode_400;

/**
 *@author 周杨
 *CountNumbersWithUniqueDigits_357 给定一个正整数n 计算0<=x<10^n的数中出现某个0-9仅一次的所有个数
 *describe:用递归 每次保存以前的结果(其实不用) AC 100%
 *2018年7月8日 下午3:35:42
 */
public class CountNumbersWithUniqueDigits_357 {
	int n;
	public static void main(String[] args) {
		CountNumbersWithUniqueDigits_357 test=new CountNumbersWithUniqueDigits_357();
		System.out.println(test.countNumbersWithUniqueDigits(3));
	}
	public int countNumbersWithUniqueDigits(int n) {
		if(n==0)
            return 1;
        if(n==1)
            return 10;
        int dp[]=new int[n+1];
       int res=10;
       for(int i=2;i<n+1;++i) {
    	   dp[i]=help(i);
    	   res+=dp[i];
       }
       return res;
    }
	
	public int help(int n) {
		int res=9;
		while(n!=1) {
			res*=(11-n);
			--n;
		}
		return res;
	}
	
	
}
